import java.util.*;
public class Solution {
	/**
	 *	正数数组中的最小不可组成和
	 *	输入：正数数组arr
	 *	返回：正数数组中的最小不可组成和
	 */
	public int getFirstUnFormedNum(int[] arr) {
        //背包问题
        //假设min=2,max=10,[2,10]就为背包容量
        int min = Integer.MAX_VALUE;
        int max = 0;
        for(int i = 0;i<arr.length;i++) {
            max +=arr[i];
            min = Math.min(arr[i],min);
        }
        int[] dp = new int[max+1];
        for(int i = 0;i<arr.length;i++) {
            for(int j = max;j>=arr[i];j--) {
                //从后往前加,从前往后会加重复
                dp[j] = Math.max(dp[j],arr[i] + dp[j-arr[i]]);
            }
        }
        for(int i = min;i<dp.length;i++) {
            if(dp[i] != i) {
                return i;
            }
        }
        return max+1;
	}
}